home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 38 / Amiga Format CD38 (1999-03-15)(Future Publishing)(GB)(Track 1 of 3)[!][issue 1999-04].iso / -seriously_amiga- / programming / other / esa / examples / mergesort.ei next >
Text File  |  1999-01-25  |  3KB  |  94 lines
  1. ****************************************************************************
  2. * THIS IS NOT A STANDALONE SOURCE!
  3. * You can compile and assemble it, but you can't run it!!!
  4. *
  5. * The procedures below execute the sorting on a vector of 32bit signed inte-
  6. * gers using the MergeSort algorithm.
  7. *
  8. * Note that these are meant to be examples only, so optimization has been
  9. * sacrificed to enhance the readability (btw: ESA isn't indicated at all
  10. * for this kinda things...).
  11. *
  12. * To use them you need an integers vector of any length and an auxiliary
  13. * vector of the same length (size in bytes = number of integers * 4).
  14. ****************************************************************************
  15.  
  16. ****************************************************************************
  17. * MergeSort v1.0.1
  18. ****************************************************************************
  19. * INFO    sorts in ascending order a vector of signed long integer
  20. * SYNOPSIS    MergeSort[SouVec,AuxVec,FEI,LEI]
  21. *              a0     a1     d0  d1
  22. * IN    SouVec    ptr to vector to sort
  23. *    AuxVec    adr of auxiliary vector
  24. *    FEI    First Element Index (tipically 0)
  25. *    LEI    Last Element Index (tipically # of integers-1)
  26. * NOTE    vector elems are .l
  27. ****************************************************************************
  28.  
  29.     procedure MergeSort[a0-a1/d0-d1],d2-d3
  30.     when.s d0«d1
  31.  
  32.      move.l    d0,d3
  33.      add.l    d1,d3
  34.      lsr.l    #1,d3    ;(FEI+LEI)/2
  35.      MergeSort[sav:a0,a1,d0,d3]
  36.  
  37.      addq.l    #1,d3    ;(FEI+LEI)/2+1
  38.      MergeSort[sav:a0,a1,d3,d1]
  39.  
  40.      move.l    d1,d2
  41.      Merge[sav:a0,a1,d0,d3,d2]
  42.  
  43.     ewhen
  44.     eproc
  45.  
  46. ****************************************************************************
  47. * Merge v1.0.1
  48. ****************************************************************************
  49. * INFO    core of MergeSort algo
  50. * SYNOPSIS    Merge[SouVec,AuxVec,FHI,SHI,LEI]
  51. *          a0     a1     d0  d1  d2
  52. * IN    SouVec    ptr to vector to sort
  53. *    AuxVec    ptr to auxiliary vector
  54. *    FHI    First Half Index
  55. *    SHI    Second Half Index
  56. *    LEI    Last Elem Index
  57. ****************************************************************************
  58.  
  59.     procedure    Merge[a0-a1/d0-d2],a0/d3-d7
  60.     move.l    d0,d3    ;i=FHI
  61.     move.l    d0,d4    ;FHI
  62.     move.l    d1,d5    ;SHI
  63.  
  64.     while.s d3«=d2    ;while i<=LEI
  65.  
  66.      when.s d4=d1    ;if FH elems over
  67.                   move.l    (a0,d5.l*4),(a1,d3.l*4)    ;AuxVec[i]=SouVec[SHI]
  68.       addq.l    #1,d5    ;inc SHI
  69.      owhen  d5»d2    ;if SH elems over
  70.       move.l    (a0,d4.l*4),(a1,d3.l*4)    ;AuxVec[i]=SouVec[FHI]
  71.       addq.l    #1,d4    ;inc FHI
  72.      othw
  73.       move.l    (a0,d4.l*4),d6    ;SouVec[FHI]
  74.       move.l    (a0,d5.l*4),d7    ;SouVec[SHI]
  75.  
  76.       when.s d6<=d7    ;if SouVec[FHI]<=SouVec[SHI]
  77.        move.l    d6,(a1,d3.l*4)    ;AuxVec[i]=SouVec[FHI]
  78.        addq.l    #1,d4    ;inc FHI
  79.       othw        ;if SouVec[FHI]<SouVec[SHI]
  80.        move.l    d7,(a1,d3.l*4)    ;AuxVec[i]=SouVec[SHI]
  81.        addq.l    #1,d5    ;inc SHI
  82.       ewhen
  83.  
  84.      ewhen
  85.  
  86.      addq.l    #1,d3    ;inc i
  87.     ewhile
  88.  
  89.     for d3 = d0 upto d2
  90.      move.l    (a1,d3.l*4),(a0,d3.l*4)
  91.     next.s
  92.  
  93.     eproc
  94.